#define  _CRT_SECURE_NO_WARNINGS
#include "Tree.h"
#include "Queue.h"

void BinaryTreeInit(TreeNode* root)
{
	assert(root);
	root->left = nullptr;
	root->right = nullptr;
	root->val = 0;
}


TreeNode* BinaryBuyNewNode(int x)
{
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	assert(newnode);
	newnode->left = nullptr;
	newnode->right = nullptr;
	newnode->val = x;
	return newnode;
}

void PreOrder(TreeNode* root)
{
	if (nullptr == root)
	{
		return;
	}
	PreOrder(root->left);
	cout << root->val << "->";
	PreOrder(root->right);
}

void MidOrder(TreeNode* root)
{
	if (nullptr == root)
	{
		return;
	}
	cout << root->val << "->";
	MidOrder(root->left);
	MidOrder(root->right);
}

void PostOrder(TreeNode* root)
{
	if (nullptr == root)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	cout << root->val << "->";

}


int BinaryTreeSize(TreeNode* root)
{
	if (root == nullptr)
	{
		return 0;
	}

	return 1+ BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);
}

int BinaryTreeLeafSize(TreeNode* root)
{
	if (nullptr == root)
	{
		return 0;
	}
	if (root->left == nullptr && root->right == nullptr)
	{
		return 1;
	}
	return  BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeLevelKsize(TreeNode* root, int k)
{
	if (nullptr == root)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKsize(root->left, k - 1) + BinaryTreeLevelKsize(root->right, k - 1);
}

int BinaryTreeDeep(TreeNode* root)
{
	if (nullptr == root)
	{
		return 0;
	}
	int left = BinaryTreeDeep(root->left);
	int right = BinaryTreeDeep(root->right);
	return left >= right ? 1 + BinaryTreeDeep(root->left) : 1 + BinaryTreeDeep(root->right);
}

TreeNode* BinaryTreeFind(TreeNode* root,int x)
{
	if (nullptr == root)
	{
		return nullptr;
	}
	if (root->val == x)
	{
		return root;
	}
	TreeNode* left =  BinaryTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	TreeNode* right = BinaryTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return nullptr;
}

void BinaryTreeDestroy(TreeNode* root)
{
	if (nullptr == root)
	{
		return;
	}
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
	root = nullptr;
}
void BinaryTreeLevel(TreeNode* root)
{
	Queue q;
	QueueNodeInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		TreeNode* front =  QueueTop(&q);
		cout << front->val << "->";
		QueuePop(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

}


bool BinaryTreeComplete(TreeNode* root)
{
	Queue q;
	QueueNodeInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueTop(&q);
		QueuePop(&q);
		if (front == nullptr)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueTop(&q);
		QueuePop(&q);
		if (front != nullptr)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
